package com.zk.algorithm.string;

import com.zk.algorithm.annotation.LeetCode;
import com.zk.algorithm.annotation.Medium;

/**
 * A -> 1
 * B -> 2
 * ...
 * Z -> 26
 *
 * 对比 {@link TransNumToString}
 */
@LeetCode("91")
@Medium
public class DecodeWays {

    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }

        int[] memo = new int[n + 1];
        memo[n] = 1;
        memo[n - 1] = s.charAt(n - 1) != '0' ? 1 : 0;

        // DP 方程实际上就是 dp[n] = dp[n-1] + dp[n-2]
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                continue;
            } else {
                int num = Integer.parseInt(s.substring(i, i + 2)); // 两个字符
                // 1 5 7
                // i
                //
                // 57 <= 26，所以 57 必须分开处理，所以 memo[i] = memo[i + 1] + memo[i + 2]
                //
                // ================================================
                // 1 2 3
                // i
                //
                // 23 <= 26，所以 23 可以作为一个整体，所以 memo[i] = memo[i + 1]
                memo[i] = (num <= 26) ? memo[i + 1] + memo[i + 2] : memo[i + 1];
            }
        }

        return memo[0];
    }

}
